I. Field of the Invention
The present invention relates generally to the field of communications, as well as to the field of data sequence generators. More particularly, many embodiments of the invention relate to pseudorandom noise (PN) sequence generators for use in Direct Sequence Spread Spectrum (DSSS) communication systems.
II. Description of the Related Art
In direct sequence spread spectrum (DSSS) communication systems, such as Code Division Multiple Access (CDMA) systems, pseudorandom noise (PN) sequences are used to generate spread spectrum signals by increasing the bandwidth (i.e., spreading) of a baseband signal. In conventional methods, PN sequences are generated with PN generators that make use of Linear Feedback Shift Registers (LFSRs). An LFSR has a shift register of N stages and intervening exclusive-OR gates for programming a specific PN sequence. A subset of the PN sequences generated by the N-stage LFSR are characterized as maximal length (ML) PN sequences, and are of length 2Nxe2x88x921.
As an example, an ML PN sequence of length seven: (1) may be characterized as having seven states: (2) has associated with it six versions of the Nominal PN Sequence shifted by a non-zero number of PN chips; and (3) has three delay elements are required for operation. FIG. 1 is a block diagram of a conventional LSFR 100 for generating an ML PN sequence of length seven. LFSR 100 has three delay elements 102, 104, and 106, and adder 108, a clock signal 110, and an output 112 providing the PN sequence. Addition is performed modulo two by adder 108. Clock signal 110 having a frequency equivalent to the rate of change of the state of the PN output sequence generated at output 112.
Table 1 below sets forth the six shifted versions of a periodic Nominal PN Sequence of length seven produced by LFSR 100 of FIG. 1. The bit patterns included with each row of the PN Sequence column correspond to the sequential values of the PN output sequence at output 112 (FIG. 1).
Table 2 below provides a representation of the value of a nominal PN output sequence at output 112 as a function of the state of LFSR 100. The sequence of three bits within each row of the left hand column of Table 2, correspond (from left to right) to the outputs of delay elements 102, 104, and 106 (from left to right). The corresponding value of the output bit (i.e., chip) produced by LFSR 100 in response to a given LFSR state is set forth in the right hand column.
In the communication systems where these LFSRs are used, it is often necessary to obtain shifted versions of PN sequences as well. Most desirable, shifted PN sequences need to be obtained in a time effective and direct manner (i.e., somewhat immediately). In direct sequence transmitters, for example, PN sequence shifting is required to enable the output of the transmitter""s PN sequence generator to be aligned with some particular system time. In direct sequence receivers, PN sequence shifting is necessary to align the output of the receiver""s PN sequence generator to the timing of a received waveform so as to enable despreading. In addition, PN sequence shifting is required for purposes of PN timing acquisition and multipath detection.
For any PN sequence of length L, there exists Lxe2x88x921 versions of the sequence which may be defined based on non-zero shifts of the sequence with respect to a reference sequence (xe2x80x9cNominal PN Sequencexe2x80x9d). The Lxe2x88x921 shifted versions of the PN sequence of length L may be derived by delaying the Nominal PN Sequence by from one to Lxe2x88x921 PN chips. Circuits similar to the LFSR 100 of FIG. 1 may be augmented with sequence shifting circuitry to enable generation of an arbitrarily shifted version of a given PN sequence.
A block diagram of a conventional LFSR circuit 200 is shown in FIG. 2 which provides arbitrarily shifted versions of a PN sequence having a length of seven. This conventional technique is based on the use of a modulo two sum of outputs of particularly selected delay elements of an additional LFSR (although a single LFSR may be used). Such techniques are predicated on the mathematical property that all possible shifted versions of a Nominal PN Sequence may be obtained through the modulo two addition of appropriately selected delay elements.
LFSR circuit 200 includes a primary LFSR 202, a secondary LFSR 204, and a masking circuit 206. As indicated, the state of the primary LFSR 202 is conveyed to secondary LFSR 204 by providing the value of each delay element within the primary LFSR 202 to a corresponding delay element within secondary LFSR 204. Although the PN sequence produced by secondary LFSR 204 will be identical to the Nominal PN Sequence produced by primary LFSR 202, the PN sequence produced by mask circuit 206 will be shifted from the Nominal PN Sequence by an offset in the manner described below. By coupling other secondary LFSRs and associated mask circuits to primary LFSR 202, a set of PN sequences of different offsets relative to the Nominal PN Sequence may be generated.
LFSR circuit 200 includes a set of two adders for performing modulo two addition. The adders are incorporated within the LFSR circuit 200 in such a manner that the Nominal PN sequence, the PN sequence, and the shifted PN sequence are all maximal length. The AND elements function to select outputs of the delay elements in accordance with the selection values M1, M2, and M3 provided by a controller (not shown). An active (binary value 1) selection value enables the output of the corresponding delay element to be summed modulo two at the adder with the outputs of other delay elements so selected, and an inactive selection value prevents the sum from occurring.
Table 3 below sets forth the six shifted versions of a periodic Nominal PN Sequence of length seven produced by LFSR circuit 200 of FIG. 2. The bit patterns included within each row of the PN Sequence column correspond to the sequential values of a particular shifted PN output sequence. As is indicated in Table 3, each PN output sequence is shifted relative to the Nominal PN Sequence by an amount determined by the combination of the selections of M1, M2 and M3.
During operation, secondary LFSR circuit 204 is provided with a load signal (not shown) which causes the delay elements to latch the LFSR state registered by the corresponding delay elements of primary LFSR circuit 202. This causes the PN sequence provided by secondary LFSR 204 upon the output line to become aligned with the Nominal PN Sequence. However, such alignment will be maintained only so long as the clock signals provided to primary LFSR 202 and secondary LFSR 204 do not differ. When such a difference in clock signals arises, the PN sequence produced by secondary LFSR 204 will no longer be aligned with the Nominal PN Sequence.
No relationships are known to exist between the desired shift and the mask needed to generate such shift. Therefore, these masks are stored in a lookup table and accessed when a particular shift is desired. However, much memory space is consumed even if a limited number of masks are stored in connection with a PN sequence having a relatively long length. For example, 15,360 mask bits need to be stored if 512 masks are used in connection with a PN sequence having length 215xe2x88x921. After using a mask to obtain a xe2x80x9ccoarsexe2x80x9d PN shift, subsequent slewing is required which consumes additional time to obtain the desired shift. As apparent, the use of LFSRs to generate PN sequence shifts is relatively complex and by no means straightforward in its approach.
In addition to shifting, it is often desirable to be able to determine the extent to which a particular (shifted) PN sequence is of set relative to a Nominal (unshifted) PN Sequence. That is, it is desirable to be able to read the current state or offset at which a particular PN sequence resides. For the LFSR circuit 200 of FIG. 2, the offset may by ascertained in a conventional fashion based on the states (i.e., the contents of the delay elements) of both LFSR 202 and secondary LFSR 204, which is relatively complicated.
Furthermore, techniques for extending the length of a given ML PN sequence from 2Nxe2x88x921 to 2N were developed because ML PN sequences having length 2Nxe2x88x921 were not convenient in application. For example, U.S. Pat. No. 5,228,054 describes a PN generator that increases the length of ML PN sequence by one PN bit (or chip) so as to provide a PN sequence that is a power of two (i.e., 2N) sequence length. These techniques, however, require the use of additional complex circuitry. For example, additional circuitry is needed for the detection of the appropriate xe2x80x9cstuff statexe2x80x9d in which to insert an additional sequence bit (xe2x80x980xe2x80x99), as well as that circuitry needed for the insertion of the additional bit (xe2x80x980xe2x80x99).
As apparent, existing techniques are generally undesirable in that they are relatively complex and inflexible. There are only a limited number of LFSRs for a given N; the length of such sequences is restricted to 2Nxe2x88x921. Thus, LFSR techniques are limited in that they are not readily capable of generating any arbitrary data sequence, and are not readily capable of generating a sequence of arbitrary length. The LFSR circuit configuration must change if some other sequence is desired, which undesirably implicates the entire system design.
As to other aspects of the system, a forward link waveform transmitted by the base station may be comprised of a pilot waveform and a data waveform. Both of the waveforms are received with the same relative phase and amplitude distortions introduced by the channel. The pilot waveform is an unmodulated PN sequence which aids in the demodulation process, as is well-known in the art as xe2x80x9cpilot-aided demodulation.xe2x80x9d Conventional pilot-aided demodulation methods typically include the steps of (i) demodulating the pilot waveform, (ii) estimating the relative phase and amplitude of the pilot waveform, (iii) correcting the phase of the data waveform using the estimated phase of the pilot waveform, and (iv) adjusting the weight of data symbols used in maximal ratio combining in a RAKE receiver based on the estimated amplitude of the pilot waveform. Steps (iii) and (iv) above are performed as a xe2x80x9cdot productxe2x80x9d as is known in the art. In some conventional methods, a controller having a central processing unit (CPU) and and/or a digital signal processor (DSP) performs each step described, including the dot product function. The dot product function, however, is computationally intensive, and typically places an undue and undesirable burden on the processor. In other conventional methods, hardware performs each step described. This approach, however, limits the flexibility in the filtering structure and selection of filter coefficients.
Accordingly, there is a need for new methods and devices to overcome these and other deficiencies of the related art, and especially a need for methods and devices to simplify data generators and system circuitry operating in connection with the same.
As one of the many inventive methods and devices described herein, a method of generating one or more data sequences for spread spectrum communications includes the steps of providing data at an input of a memory which stores bits associated with a pseudorandom noise (PN) sequence; changing the data; and for each of a plurality of changes of the data, providing a selected PN bit of the PN sequence at an output of said memory based on the data.